package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 恢复二叉树
 * https://leetcode.cn/problems/recover-binary-search-tree/
 *
 * @time 2024/1/5
 */
public class RecoverTree {

    public void recoverTree(TreeNode root) {
        search(root);
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        fixTree(root);
    }

    private int index = 0;

    private void fixTree(TreeNode root) {
        if (null == root) {
            return;
        }
        fixTree(root.left);

        Integer val = list.get(index);
        index++;
        if (root.val != val) {
            root.val = val;
        }

        fixTree(root.right);
    }


    List<Integer> list = new ArrayList<>();

    private void search(TreeNode root) {
        if (null == root) {
            return;
        }
        search(root.left);
        list.add(root.val);
        search(root.right);
    }
}
